\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\textbf{区间离散化}

常规的区间离散化即将一个大区间中的信息"折叠"，然后保留左右端点，并将左右端点的值离散化

比如：

\begin{quote}
区间 \([5 , 1000]\)，将 \([6,999]\)
中的信息折叠，再离散化\(<5 , 1000>\)→\(<1 , 2>\)\\
那么最后 \([1 , 2]\) 即为离散化后的 \([5,1000]\)
\end{quote}

但当涉及到多个区间时这么做会出现一些问题，比如：\\
有两个区间分别为：\([1,2]\),\([5 , 6]\)，离散化后它们分别为：\([1 , 2]\),\([3,4]\)\\
而原本 \([1 , 2],\)\([5,6]\) 并不是连续区间，但离散化后
\([1,2]\),\([3,4]\)就成了连续区间，区间之间的关系发生改变，那么离散化就是错误的，我们不能忽略两区间之间的区间

\textbf{权值线段树区间离散化}

再补充一下上面的问题：

\begin{itemize}
\item
  普通权值线段树的叶子节点存储的是一个\textbf{数}的信息
\item
  而权值线段树区间离散化的叶子节点存储的是一个\textbf{折叠区间}的信息
\item
  对于一棵线段树，它的叶子节点对应的数需要连续。\\
  因为线段树规定两个叶子节点的父节点对应的区间是两叶子节点之间的所有数
\item
  所以权值线段树区间离散化的叶子节点对应的信息也必须连续\\
  这样才能保证父节点覆盖了子节点之间所有的信息
\end{itemize}

所以如果按照普通的离散方式建立线段树，有些存在的区间就会被忽略

于是我们可以按照左闭右开的方式离散化：\\
对于区间
\([1 , 2]\),\([5,6]\)，先将其改为左闭右开的形式→\([1,3)\),\([5,7)\)\\
离散化之后对应的区间就是\([1 , 2)\),\([3,4)\)\\
再还原回去→\([1,1],[3,3]\)，这样就不会造成区间的丢失

\textbf{时间分治}：通常搭配可撤销并查集使用（例题写在可撤销并查集那块了）

\end{document}
